package com.its.myalgorithm.day03;

import com.its.myalgorithm.day01.ArrayUtils;

/**
 * @projectName: dgl-algorithm
 * @package: com.its.myalgorithm.day03
 * @className: BSAwesome
 * @author: DONG GL
 * @description: TODO 局部最小
 * @date: 2022/3/31 11:33
 * @version: 1.0
 */
public class BSAwesome {
    // arr 相邻的数不相等！ 找出一个局部最小
    public static int oneMinIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int len = arr.length;
        if (len == 1) {
            return 0;
        }
        //局部最小第一种情况
        if (arr[0] < arr[1]) {
            return 0;
        }
        //局部最小第二种情况
        if (arr[len - 2] > arr[len - 1]) {
            return len-1;
        }
        //否则 进行二分查找
        int L =0;
        int R = len-1;
        while (L < R-1) {
            int mid = (L + R) / 2;
            if (arr[mid] < arr[mid + 1] && arr[mid] < arr[mid - 1]) {
                return mid;
            }else {
                if (arr[mid] > arr[mid - 1]) {
                    //抛弃右边
                    R = mid-1;
                }else {
                    L = mid+1;
                }
            }
        }

        return  arr[L] < arr[R] ? L : R;
    }

    // 生成随机数组，且相邻数不相等
    public static int[] randomArray(int maxLen, int maxValue) {
        //随机生成数组
        int len = (int) (Math.random()* maxLen);
        int[] arr = new int[len];
        if (len > 0) {
            arr[0] = (int) (Math.random() * maxValue);
            for (int i = 1; i < len; i++) {
                do {
                    arr[i] = (int) (Math.random() * maxValue);
                } while (arr[i] == arr[i - 1]);
            }
        }
        return arr;
    }


    // 也用于测试
    public static boolean check(int[] arr, int minIndex) {
        if (arr.length == 0) {
            return minIndex == -1;
        }
        int left = minIndex - 1;
        int right = minIndex + 1;
        boolean leftBigger = left >= 0 ? arr[left] > arr[minIndex] : true;
        boolean rightBigger = right < arr.length ? arr[right] > arr[minIndex] : true;
        return leftBigger && rightBigger;
    }

    public static void main(String[] args) {
        int maxLen = 1000;
        int maxValue = 2000;
        int testTime = 1000000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr = randomArray(maxLen, maxValue);
            int ans = oneMinIndex(arr);
            if (!check(arr, ans)) {
                ArrayUtils.printArray(arr);
                System.out.println(ans);
                break;
            }
        }
        System.out.println("测试结束");
    }
}
